package main;

import java.io.File;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception { new Main(); }
	Map<String, Double> results = new HashMap<String, Double>();
	
	public Main() throws Exception {
//		long start = System.currentTimeMillis();
		
		File dir = new File("lab4/");
		for (File f: dir.listFiles()) {
			if (f.getName().endsWith(".tsp")) {
				findClosest(f);
			}
		}
		
/*		long time = System.currentTimeMillis()-start;
		double s = (time%60000);
		s /= 1000;
		time /= 60000;
		long m = time%60;
		time /= 60;
		long h = time;*/
	}
	
	void findClosest(File f) throws Exception {
		List<Coord> list = new ArrayList<Coord>();
		int points=-1;
		
		Scanner scan = new Scanner(f);
		String line;
		while (true) {
			line = scan.nextLine();
			if (!(line.charAt(0) > 'A' && line.charAt(0) < 'Z')) {
				break;
			}
		}
		while (true) {
			++points;
			String[] split = line.split("[ \t]+");
			String name = split[0];
			if (!name.equals("EOF")) {
				try {
					double x = Double.parseDouble(split[1]);
					double y = Double.parseDouble(split[2]);
					list.add(new Coord(x, y, name));
				} catch (Exception e) {
					System.out.println(f.getName());
					System.out.println("..: "+ split[0]);
				}
			}
			if (scan.hasNext()) {
				line = scan.nextLine().trim();
			} else {
				break;
			}
		}
		
		java.util.Collections.sort(list);
		double min = find(list);

	//	System.out.print(f.getName() +": "+ points +" ");
	//	System.out.println(Math.sqrt(min));
		
		results.put(f.getName(), min);
	}
	
	double find(List<Coord> list) {
		if (list.size() == 1) {
			return Double.POSITIVE_INFINITY;
		} else if (list.size() <= 3) {
			double min=Double.POSITIVE_INFINITY;
			for (Coord c: list) {
				for (Coord d: list) {
					if (c != d) {
						min = min(min, dist(c, d));
					}
				}
			}
			return min;
		}
		
		int half = list.size()/2;
		List<Coord> l1 = list.subList(0, half);
		List<Coord> l2 = list.subList(half, list.size());
		
		double min = min(find(l1), find(l2));
		double left = (l1.get(l1.size()-1).x+l2.get(0).x)/2-min;
		double right = (l1.get(l1.size()-1).x+l2.get(0).x)/2+min;
		
		List<Coord> ysorted = new ArrayList<Coord>();
		for (int i=l1.size()-1; i>=0; --i) {
			if (l1.get(i).x > left) {
				ysorted.add(l1.get(i));
			} else {
				break;
			}
		}
		for (int i=0; i<l2.size(); ++i) {
			if (l2.get(i).x < right) {
				ysorted.add(l2.get(i));
			} else {
				break;
			}
		}
		
		Collections.sort(ysorted, new Ysort());
		
		for (int i=0; i<ysorted.size(); ++i) {
			Coord check = ysorted.get(i);
			for (int k=1; k<16 && i+k<ysorted.size(); ++k) {
				min = min(min, dist(check, ysorted.get(i+k)));
			}
		}
		
		return min;
	}
	
	double dist(Coord c, Coord d) {
		double i = Math.sqrt((c.x-d.x)*(c.x-d.x)+(c.y-d.y)*(c.y-d.y));
		return i;
	}
	
	double min(double a, double b) {
		return a<b? a: b;
	}
}

class Coord implements Comparable {
	double x, y;
	String name;
	
	public Coord(double x2, double y2, String name) {
		this.x = x2;
		this.y = y2;
		this.name = name;
	}
	public Coord(){}
	
	@Override
	public int compareTo(Object arg0) {
		Coord c = (Coord)arg0;
		if (x > c.x) {
			return 1;
		} else if (x < c.x){
			return -1;
		} else {
			return 0;
		}
	}
	public String toString() {
		return name+":("+x+", "+y+")";
	}
}

class Ysort implements Comparator<Coord> {

	public int compare(Coord c, Coord d) {
		if (c.y > d.y) {
			return 1;
		} else if (c.y == d.y) {
			return 0;
		} else {
			return 1;
		}
	}
}